#include <iostream>
#include <vector>
#include <deque>

using namespace std;
// 239. 滑动窗口最大值
// 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
// 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
// 返回 滑动窗口中的最大值 。

// 使用双端队列。滑动窗口不断向前滑动
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(k == 0 || nums.size() == 0)
            return vector<int>();
        if(k == 1)
            return nums;

        deque<int> window;  // 存放当前滑动窗口的下标
        vector<int> res;

        for(int i = 0; i < nums.size(); i++) {
//            cout << "i = " << i <<"."<<endl;
            if(i >= k && window[0] <= i-k)
                window.pop_front(); // 窗口往右滑动，最左边的元素出队

            // 下一个要加入的元素nums[i]大于队列中的元素，则队列的元素要出队
            while(window.size()>0 && nums[window[window.size() - 1]] <= nums[i])
                window.pop_back();

            window.push_back(i);

            if(i >= k - 1)
                res.push_back(nums[window[0]]);

//            printSlidingWindow(window); // 测试滑动窗口
        }
        return res;
    }

private:
    void printSlidingWindow(deque<int>& window) {
        cout << "window: [ ";
        for(int i = 0; i < window.size(); i++) {
            cout<<window[i];
            if(i != window.size() - 1) {
                cout<<", ";
            }
        }
        cout << " ]" << endl;
    }
};
void print_vec(const vector<int>& vec){
    for(int e: vec) cout << e << " "; cout << endl;
}
int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    print_vec(Solution().maxSlidingWindow(nums, 3));
    return 0;
}
